package net.lxch.service;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Tian {
    private HashSet<Integer> V;

    private HashSet<Integer> X;

    private HashSet<Integer> Y;

    private ArrayList<Integer> L;

    private int[][] table = new int[][]{{0, 0, 0, 0, 0, 0, 0}, {0, 0, 9, 4, 0, 0, 0},

            {0, 0, 0, 0, 12, 5, 0}, {0, 0, 4, 0, 0, 13, 0},

            {0, 0, 0, 0, 0, 0, 2}, {0, 0, 0, 0, 3, 0, 15},

            {0, 0, 0, 0, 0, 0, 0}};


    /**
     * 构造
     */

    public Tian() {

        preInit();

        DIJKSTRA();

        printL();

        printtable();

        System.out.println("L:" + L + "/nV:" + V + "/nX:" + X + "/nY:" + Y);

    }


    /**
     * 数据初始化
     */

    public void preInit() {

        int[] v = {1, 2, 3, 4, 5, 6};

        V = new HashSet<>();//存放顶点名称

        for (int i = 0; i < v.length; i++)

            V.add(v[i]);

        X = new HashSet<>();

        X.add(1);//集合X存放源点1

        Y = new HashSet<>(V);//集合Y初始化

        Y.remove(1);//Y = V -｛1｝

        L = new ArrayList<>(7);

        for (int j = 0; j < 7; j++)

            L.add(Integer.MAX_VALUE);

        L.set(1, 0);

    }


    /**
     * 算法DIJKSTRA
     */

    public void DIJKSTRA() {


        System.out.println("V.size():" + V.size());

        for (int y = 2; y <= V.size(); y++) {

            if (table[1][y] > 0)// 如果y相邻于1

                L.set(y, length(1, y));

            else

                L.set(y, Integer.MAX_VALUE);

        }

        for (int j = 1; j <= V.size() - 1; j++) {

            int y = findTheMinInL();

            X.add(y);

            Y.remove(y);

            for (int jj = 1; jj < table.length; jj++) {

                if (table[y][jj] > 0)

                    if (Y.contains(jj)

                            && ((L.get(y) + length(y, jj)) < L.get(jj)))

                        L.set(jj, L.get(y) + length(y, jj));

            }

        }

    }


    /**
     * 返回L中最小的数的index
     */

    public int findTheMinInL() {

        Iterator<Integer> it = L.iterator();

        int temp = Integer.MAX_VALUE;

        while (it.hasNext()) {

            int its = it.next();

            if (Y.contains(L.indexOf(its)) && its <= temp)//错误发现前if (Y.contains(its) && its <= temp)

                //这句话是  ：令y∈Y，使得L[y]为最小

                temp = its;

        }

        return (L.indexOf(temp));

    }


    /**
     * 求a,b两顶点的距离（最短）
     */

    public int length(int a, int b) {//根据table[][]查询并返回int长度

        if (table[a][b] > 0)

            return table[a][b];

        else

            return Integer.MAX_VALUE;

    }


    /**
     * 打印图信息
     */

    public void printtable() {

        System.out.println("");

        System.out.println("图的信息:");

        for (int i = 1; i < table.length; i++) {

            for (int j = 1; j < table.length; j++) {

                System.out.printf("%3d", table[i][j]);

            }

            System.out.print("/n");

        }

    }


    /**
     * 打印各个顶点的最短路径信息
     */

    public void printL() {

        System.out.println("各个顶点从1点出发的最短路径为：");

        for (int i = 1; i < L.size(); i++) {

            int temp = L.get(i);

            System.out.print(temp + "       ");

        }

    }


    /**
     * mainBase
     */

    public static void main(String[] args) {

        new Tian();

    }
}
